Modern high speed networks use a new set of standards collectively termed ATM (Asynchronous Transfer Mode). Referring to FIG. 1, in ATM computer networks data packets 100 transmitted over the network are fragmented into smaller cells 110 for transmission over the network. Each cell 110 is 53 bytes long, including a five-byte header 112 and a 48-byte cell payload (i.e., data) 114. Each cell's header 112 includes a "virtual connection identifier" 116, discussed below, and a END flag 118 that is set only for the last cell of each data packet. Data packets that are 48 bytes or less in length are transmitted as single cell (also called unicell) messages.
Furthermore, as shown in FIG. 2, the cells of a data packet may need to be routed through a number of switches 120 during transport from a sourcing host computer A 122 to a destination host computer 124.
To allow very high data rates (in the hundreds of Mb/s and above) the switching time of a cell in every switch 120 along the route must be minimal. ATM networks achieve this by means Of a label swapping mechanism which requires a set up phase before the actual data stream can be transported from source to destination.
To support the transfer of data cells in the ATM network, a set of messages is defined for the set up, maintenance, and take down of the labels, bandwidth reservations and the like for each ATM connection. In order to forward these control messages, either the entire route must be supplied with each message, or the message can be forwarded based on the labels already set up for an existing connection. The current invention is aimed at the efficient distribution of the control messages by the use of labels in a given "connection," so that the entire route to be traversed by the message need not be carried in each message.
It is noted that the terms connection, virtual connection and virtual circuit are used interchangeably in this document. More particularly, all three of these terms are defined to mean a communication channel that may include one or more interconnected virtual connection segments. Each virtual connection segment is a data channel or control channel that traverses one link between two neighboring nodes or one link between a host and node, while a connection or virtual connection (VC) is a communication channel that travels through numerous links and their connecting nodes. A "connection" is established or represented by a set of one of more virtual connection indentifiers (VCIs) stored in the VC tables of the nodes along the connection path.
The terms "node" and "switch" are also used interchangeable in this document.
Referring again to FIG. 2, at a high level, ATM networks can be viewed as a collection of A TM-switches 120 interconnected by high-speed links 128 in a networked fashion to provide ATM service to a number of external users 122, 124.
Referring to FIG. 3, a typical switch 120 is comprised of three main parts: the switching fabric 140, a buffering unit 142, and a control unit 144. The control unit 144 is divided into two parts 146, 148. The first part 146 controls the cell switching properties, i.e., it controls and coordinates the operation of the buffering unit and the switching fabric. For performance reasons, the first part 146 of the control unit is typically implemented in hardware such as a VC lookup table 147, finite state machines, and so on. The second part 148 of the control unit is responsible for all other control functions such as preparing and maintaining the switching tables, coordinating activities with other switches and with network management facilities, and serving individual user requests. We refer to this second part of the control unit as the control point (CP) of the switch. In our terminology the switch contains the switching fabric, the buffering unit, and the basic core of the control unit, whereas the switch and the CP together will be referred to as an ATM node (or node, for short). The CP 148 is essentially a logical entity which is typically implemented using control software 150 executing on a general purpose microprocessor 152, although firmware and other software/hardware configurations are also possible. A configuration in which a single CP controls several switches is also possible. For example, if the particular way in which a switch is implemented lends itself to the efficient interconnection of several switches (typically of the same kind) then it would be natural to have this set of switches controlled by a single CP.
The physical device on which the CP is implemented is termed the Controlling Device (CD). The CD may not be a single entity, since pads of the CP can be implemented in different hardware pieces. For example, each link adaptor of a switch could contain a separate micro-controller and possibly an additional central micro-processor could be responsible for the common switch functions. Another implementation option is a single CD that hosts several CPs, each controlling a different switch and possibly communications with each other within the same CD.
Two CPs are called neighbors if they control two switches 120 that are directly connected by a link 128. A CP is a uniquely identifiable entity within the network. That is, it is possible to name a CP as the endpoint of a virtual connection (VC) and switches can identify cells destined to the CP and forward them appropriately. This is the mechanism by which control messages can be exchanged between CPs.
Every switch 120 in the network possesses a unique ID, which is assigned to it at configuration time. This ID, termed the switch ID, is guaranteed to be unique only within the network. Links 128 can have IDs that are local to the switch from which they emanate. This allows the use of shod local link IDs, which is beneficial since local link IDs are frequently used. Therefore, to globally identify a link, some combination of a CP ID, node ID and link ID must be used. Link, switch and CP IDs appear in the messages that are exchanged between CPs and hence it is beneficial to choose as short a descriptor as possible.
In general, CPs perform those functions that are necessary to make a group of switches operate as an integrated network. The process of integration entails understanding of and compensation for the differences between switches of different makes and models. One of the most important functions is that of virtual connection (circuit) management which includes VC set-up, maintenance and VC take down. To perform these functions properly the CP must maintain information regarding network topology and its level of utilization (e.g., available bandwidth on various links with respect to every class of service). Each control point's control software includes a network topology information maintenance procedure 150A for the purposes of retaining up-to-date network topological information. Topological data typically changes very infrequently while utilization data, as explained above (and by design), changes very frequently.
To achieve their functions, CPs obviously need to communicate with one another either directly or indirectly. The control mechanism typically requires CPs to mostly communicate with neighbor CPs. In many cases a message arriving at a CP may trigger the transmission of another message. For example, if a topological change has occurred in the network, a CP will typically notify other CPs (e.g., its neighbors) of the change; each of the recipients of this message may, in turn, generate new messages to further distribute the information. We define a control link as the channel over which two CPs communicate. The collection of control links must enable every CP to distribute the appropriate data to every other CP. In a typical design, there will be a control link between any two neighboring CPs.
One way of forwarding messages along a desired path within an ATM network is to provide a list of each link to be traversed along the path from source to destination. This method may be referred to as the source route method since the source supplies the entire route to be traversed by the message. A source route message may be used, for instance, to set up an ATM connection along a path specified in the message. In the case where a connection has already been established, the source route message is inefficient since it has to carry a large amount of redundant information.
In ATM networks a tree is typically set up by a VC set up procedure 150B, using set up messages. A set up message is a particular type of source route message. The VC set up procedure 150B sends one or more VC set up messages, and those VC set up messages are routed through the ATM network such that they are received by the CPs of all the nodes in the connection to be established.